1. Technical Field
The invention relates generally to image processing systems, and, more particularly, to image processing systems that utilize polyhedral environment maps to create and view three dimensional images from data representing multiple views of a scene.
2. Description of the Related Art
An environment map is a data structure representing the colors and/or other information that is characteristic of a set of samples defined with respect to a fixed point in space. A complete environment contains data for a set of directional samples distributed over all possible angles (4.pi..sup.2 steradians). A partial environment map may represent any subset of the possible solid angles. The directional samples are all defined with respect to a single point in space which forms the origin or center of the environment map.
The data contained in an environment map may be used to determine an image that is characteristic of any direction and field of view contained within the solid angles represented by the environment map. The image is typically composed of a rectangular grid of elements or pixels, each of which is characteristic of a direction with respect to the origin of the environment map. The characteristic direction the elements of the image may be associated with one or more directional samples of the environment map. In the simplest case, known as a point-sampled image, each element of the image is associated with the single sample of the environment map that corresponds to a direction that most closely matches the direction associated with the element of the image. More elaborate sampling and filtering techniques are also possible in which each element of the image is associated with multiple samples of the environment map that corresponds to directions that match the directions associated with the element of the image.
An environment map may also be used to approximate the effects of light reflected by the surface of a three dimensional object located at or near the origin of the environment map. For example, consider a point on a three dimensional object which is characterized by coordinates (xp,yp,zp) and a unit normal vector N. In order to generate a view of the object from a direction DO, the color associated with the object at the coordinates (xp,yp,zp) may be determined partly or entirely by the values of the environment associated with the Direction De=D-2N*(N.multidot.D).
In principle, any set of flat or curved surfaces may be used to define an environment map. For example, the QuicktimeVR product from Apple Corp of Cupertino, Calif., utilizes a cylindrical environment map to support panoramic image generation and the RenderMan product from Pixar Animation Studios of Port Richmond, Calif. uses both spherical environment maps and environment maps based on six sides of a cube. All of these examples take advantage of the ability to represent the constituent surfaces with a rectangular two dimensional coordinate system. The cylindrical environment map is based on azimuth and elevational coordinates. The spherical environment map uses latitude and longitude coordinates. The cube-face environment map utilizes standard row and column addressing for each of the six faces of the cube.
Each of these environment maps have distinct limitations that restrict their usefulness.
The spherical environment map has an inefficient distribution of samples with higher densities of samples near the poles of the sphere than around the equator of the sphere. In principle, a sphere treats all directions is space equally. However, imposition of a latitude and longitude coordinate system on a sphere breaks this symmetry and requires designation of a preferred axis (i.e., the polar axis) in space. This leads to unequal treatment of the polar regions with respect to the equatorial regions. The use of latitude and longitude coordinate system also tends to require frequent evaluation of trigonometric functions which may be prohibitively intensive for use in some applications and/or systems.
More specifically, the choice of the direction of the polar axis of the spherical environment map is completely arbitrary; and, after choosing the direction of the polar axis, the resulting combination of a sphere and polar axis no longer has the full symmetry of the sphere itself. Only the symmetry of a cylinder remains. Thus, it is possible to rotate the sphere and polar axis combination about the polar axis without changing the polar axis, but rotating this combination about any other direction moves the polar axis. Moving the polar axis is equivalent to choosing a new polar axis, and this does not preserve the original polar axis choice.
After choosing a polar axis, a latitude and longitude coordinate system may be defined. The latitude and longitude coordinate system include an angle .theta. running from .pi./2 at one pole to -.pi./2 at the other pole, and a second (azimuthal) angle .phi. running from 0 to 2.pi. starting at some arbitrary direction perpendicular to the polar axis. The resulting lines of constant .theta. and constant .phi. converge on the poles. Near the "equator" (the line with .theta.=0), the lines of constant .theta. and .phi. form a rectangular grid. Near the poles, however, the lines of constant .theta. (latitude) form concentric circles around the poles, and lines of constant .phi. (longitude) form spokes radiating from the poles. The circles and spokes patterns seen near the poles is quite distinct from the grid pattern seen near the equator, but the underlying sphere has exactly the same shape in both regions. The circles and spokes patterns seen near the poles are not properties of the sphere itself. These are only consequences of the arbitrary decision to impose a polar axis on the sphere.
In contrast, the cylindrical and cube-face environment maps have relatively uniform distributions of directional samples. However, the cylindrical environment is open at both ends which prevents it from being used for view directions approaching the axis of the cylinder. The ends of the cylinder may be capped with additional top and bottom images as set forth in U.S. patent application Ser. No. 60/023,143, filed on Aug. 5, 1996 and commonly assigned to the assignee of the present application, incorporated by reference above in its entirety. However, the resulting data structure requires special treatment for directions having elevations above, within, or below the cylindrical data. In addition, the algorithms required for viewing the top and bottom images may be more laborious than the algorithms required to view the data within the cylindrical region.
With respect to the cube-face environment map, the algorithms required to determine which faces of the cube are intersected by the viewing frustrum are computationally intensive, and may impact the performance of the system.
Thus, there is a need in the art to provide for an efficient system for generating and viewing three dimensional panoramic images based environment maps, and thus provide an improved level of interactive graphical feedback.